package com.example.lcpractice.lc;

import java.util.HashSet;

/**
 * [136]只出现一次的数字.java
 * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
 * <p>
 * 说明：
 * <p>
 * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
 * <p>
 * 示例 1:
 * <p>
 * 输入: [2,2,1]
 * 输出: 1
 * 示例 2:
 * <p>
 * 输入: [4,1,2,1,2]
 * 输出: 4
 * Related Topics
 * 位运算
 * 数组
 *
 * @author hd
 * @date 2022-07-08 09:51
 * @description 回文数
 */
public class Lc136 {


    public static void main(String[] args) {
        System.out.println(singleNumber2(new int[]{4, 1, 2, 1, 2}));
    }

    /**
     * 利用集合的方式，不推荐
     * 因为最多2个，所有先加后减只剩一个就是
     * @param nums
     * @return
     */
    public static int singleNumber(int[] nums) {
        HashSet<Integer> integers = new HashSet<>();
        for (int num : nums) {
            if (integers.contains(num)) {
                integers.remove(num);
            } else {
                integers.add(num);
            }
        }
        for (Integer integer : integers) {
            return integer;
        }
        return -1;
    }

    /**
     * 1⊕0=1 因为不同为1， 0⊕0=0因为相同为0，故此 任何数与0异或都是本身
     *
     * 答案是使用位运算。对于这道题，可使用异或运算 ⊕。异或运算有以下三个性质。
     * <p>
     * 1.任何数和 0 做异或运算，结果仍然是原来的数，即 a⊕0=a。
     * 2.任何数和其自身做异或运算，结果是 0，即 a⊕a=0。
     * 3.异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。
     * <p></p>
     * 故此，偶数都被自己与自己时， 对应清零
     * 保留下奇数个，故此法不仅对2个有效，对奇偶取奇也可
     * @param nums
     * @return
     */
    public static int singleNumber2(int[] nums) {
        //0 与任何数异或都是其不变
        int re=0;
        for (int num : nums) {
            re ^= num;
        }
        return re;
    }
}
